Computers, and other network devices, communicate by sending packets to one another over a network. By analogy, a packet is much like a mailed letter. That is, a letter is like a packet's payload while the mailing address is like a network destination address stored in a packet's header.
A packet traveling across a network may make many “hops” before reaching its final destination. For example, a packet may be handled by network devices known as routers that examine a packet's destination address to determine how to forward the packet further toward its destination. Typically routers perform this task by accessing routing tables that indicate where to forward packets destined for a particular address.
Because they are numeric, network addresses can be somewhat cryptic. For example, a computer may have an Internet Protocol (IP) address of “11000000101000000000110010000001”. For convenience, this string of binary bits can be expressed as “192.160.12.129” where each of the four numbers is the decimal expression of eight of the binary bits (e.g., 192decimal represents the first eight bits, 1100000binary, of the address).
Routing tables often include entries for specific network addresses. For example, a table can specify where to forward a packet destined for address “192.160.12.129”. This is known as a “direct route” entry.
Routing tables may also include entries for collections of network addresses. For example, a routing table entry may specify where to forward packets starting with the address prefix of “192.160”. Thus, a packet destined for “192.160.11.11” and a packet destined for “192.160.99.99” would both be handled by the same table entry since they both start “192.160”. Entries for collections of addresses are known as “indirect routes”. An indirect route is often expressed as a network address followed by a prefix mask. For example, for the route “192.160.0.0/16” the “16” identifies the number of bits in the mask. Thus, in this example, the mask is 16-bits long and, therefore, the first two digits in the decimal string (i.e., “192.160”).
Potentially, multiple route entries in a routing table may overlap. For example, a direct route entry of “192.160.12.129/32” and an indirect route entry of “192.160.0.0/16” both encompass the network address “192.160.12.129”. Additionally, the routing table may include other indirect routes such as “192.160.12.0/24”. Potentially, these different entries may specify different handling information for a packet. To resolve this apparent dilemma over which route entry to use, routers can implement “best matching prefix” (a.k.a. “longest prefix matching”) algorithms. A best matching prefix algorithm selects the most specific route matching a network address (e.g., the matching route entry with the longest prefix). Thus, in this example, a packet destined for “192.160.12.129” would be handled by the direct route information stored for entry “192.160.12.129/32” which has a longer mask than “192.160.0.0/16” or “192.160.12.0/24”.